\chapter{Monitors}
Monitors, at their most general, are classes that control thread
access to resources. Java synchronization is based on the variety of
monitors that were developed in the early 1970s by Per Brinch-Hansen
and C. A. R. Hoare, but Java synchronization is not as well developed
as Brinch-Hansen and Hoare monitors are.  

In this chapter, we will compare Java's synchronization to
monitors. We will present our \lstinline'Monitor' class. This class will allow you
to use full-monitor facilities in Java, although it will not allow the
compiler to check your program for correctness, as Brinch-Hansen's and
Hoare's do. The implementation of the \lstinline'Monitor' class will
itself be instructive on how to use \lstinline'Semaphore's.

\section{Real Monitors and Java Monitors}
When Brinch-Hansen and Hoare did their work, they were faced with the
following problems: Concurrent programs were unreliable and hard to
write. Semaphores were already understood; Dijkstra had developed them
half a decade earlier, but semaphores were often used incorrectly, and
a compiler could provide no help on using them.  

What Brinch-Hansen was after was a facility for synchronizing
concurrent programs that would be easy to use and could also be
checked by a compiler.  

The first requirement for this facility is that while they are
concurrently executing, threads (processes) must be accessing
different sets of variables. When they have to access the same
variables, they must be granted mutually exclusive access. Moreover,
one thread must be able to wait for a condition that another thread
can cause.  

Brinch-Hansen and Hoare called their solution monitors. They gave this
definition of a monitor: 

\begin{quote}
A \emph{monitor} is essentially a shared class with explicit queues.
\end{quote}

Thus, it has two components: \emph{a shared class} and \emph{explicit queues}.
 We will consider them one at a time.  

\subsection{Shared Classes.}

The effect of a shared class can occur in Java by creating a class in
which all fields are private and all methods are synchronized.  

In a monitor, the only variables that can be accessed by more than one
thread are the fields of a monitor. Since the fields are private, they
cannot be accessed outside the monitor. Since the methods of the
monitor are synchronized, the accesses inside the monitor are mutually
exclusive. This meets the requirement that threads have mutually
exclusive access to shared variables.  

\subsection{Explicit Queues}

Threads must be able to wait for other threads to cause conditions. In
a monitor, the conditions are represented by condition
variables. These variables contain queues of threads waiting for the
conditions to hold.  

In the bounded-buffer example, there are two conditions that a thread
could be waiting for. If a thread wishes to read a value from the
buffer, the buffer must first contain a value. If a thread wishes to
place a value in the buffer, the buffer must not be full.  

Java has only one queue for threads waiting at an object, so in our
bounded-buffer code, we must notify all waiting threads when we put a
value into the buffer (making it non-empty) or remove a value (making
it nonfull). We must wake up all of the threads in order to see if the
buffer permits their execution. This is inefficient.  

Using true monitors, we would use two condition variables. When we put
a value in the queue, we would only wake up one thread waiting for the
queue to be nonempty. When we remove a value, we would only wake up
one thread waiting for the queue to be nonfull. The code to do this in
a dialect of Pascal might be 

%TODO do we ant a caption here?
%TODO switch to Pascal highlighting for this listing?
\begin{lstlisting}[caption=Bounded Buffer shared class in Pascal-like Syntax]
  shared class BoundedBuffer (size: integer)
    var
      notEmpty, notFull: Condition;
      hd, tl: integer;
      buffer: array 0.. size-1 of Object;

    procedure put(v: Object)
    begin
      if tl - hd >= buffer.length then
      await notFull;
      buffer[tl mod buffer.length] := v;
      tl:=tl+1;
      signal notEmpty;
    end

    function get(): Object
    begin
      var v: Object;
      if tl=hd then await notEmpty;
      v := buffer[hd mod buffer.length];
      hd:=hd+1;
      signal notFull;
      return v;
    end

    begin
      hd:=0;
      tl:=0;
    end
\end{lstlisting}

Notice that not only is there more than one queue that a thread can
wait on, but also that the threads do not wait in loops. In Java, a
thread waits in a \lstinline'while' loop testing the condition, for
example, 

\begin{lstlisting}
   while (!condition) wait();
\end{lstlisting}

In Java, the thread awakened by \lstinline'notify()' or
\lstinline'notifyAll()' does not get immediate control of the lock. By
the time the thread runs, the condition may no longer be true, so it
must check the condition again. With a monitor, however, the shared
object is immediately handed off to the thread that has been awakened,
so that when the thread starts running, the condition is guaranteed to
still be true.  

\subsection{Overall}

Monitors provide greater security from system breakdown than Java
does. Compilers for languages that support monitors can assure that
all fields that can be accessed by more than one thread are protected
by monitors. They can also assure mutual exclusion to those
fields. They can check for the possibility of deadlock due to cycles
in the graph of monitor calls. The implementation of these compilers
can guarantee that a thread waiting for a condition will gain access
to the monitor immediately, so the condition will still be true.  

Despite Java's goal of reliability and catching as many errors at
compile time as possible, it provides nowhere near the same level of
support for writing reliable concurrent programs that monitors
provide.

This led Brinch-Hansen to express a great disappointment with Java's
synchronization.  

\begin{quote}
Java's most serious mistake was the decision to use the sequential
part of the language to implement the run-time support for the
parallel features.

In 1975, Concurrent Pascal demonstrated that platform-independent
parallel programs (even small operating systems) can be written as a
secure programming language with monitors. It is astounding to me that
Java's insecure parallelism is taken seriously by the programming
language community a quarter of a century after the invention of
monitors and Concurrent Pascal. It has no merit. \footnote{Brinch-Hansen, Per, ``Java's Insecure Parallelism,'' \emph{ACM SIGPLAN Notices}, 34(4) April 1999.}
\end{quote}

\section{Class Monitor in the Thread Package}
The thread package provides the \lstinline'Monitor' class with condition
variables similar to those defined by Hoare and Brinch-Hansen. The
condition variables are provided by the inner class \lstinline'Condition'
. Of course, the syntax is not the same, and the compile-time checking
provided by monitors is not possible.  

To use a monitor to protect your class, you can have your class extend
\lstinline'Monitor', as in the following bounded-buffer example: 

%TODO this listing in examples?
\begin{lstlisting}[caption=Bounded Buffer class derived from Monitor]
class BoundedBuffer3 extends Monitor{
 Condition notEmpty = new Condition();
 Condition notFull = new Condition();

 volatile int hd=0,tl=0;
 Object[] buffer;
 public BoundedBuffer3(int size) {
    buffer = new Object[size];
 }
 public void put(Object v)
        throws InterruptedException {
    enter();
    if(tl - hd >= buffer.length) notFull.await();
    buffer[tl++ % buffer.length] = v;
    notEmpty.signal();
    leave();
 }
 public Object get()
        throws InterruptedException {
    enter();
    Object v;
    if (tl==hd) notEmpty.await();
    v = buffer[hd++ % buffer.length];
    notFull.signal();
    leave();
    return v;
 }
}
\end{lstlisting}

Or, you can use a separate \lstinline'Monitor' object: 

%TODO this listing in examples?
\begin{lstlisting}[caption=Bounded Buffer class using Monitor instance.]
class BoundedBuffer4 {
 Monitor mon = new Monitor();
 Monitor.Condition notEmpty = mon.new Condition();
 Monitor.Condition notFull = mon.new Condition();

 volatile int hd=0,tl=0;
 Object[] buffer;
 public BoundedBuffer4(int size) {
    buffer = new Object[size];
 }
 public void put(Object v)
        throws InterruptedException {
    mon.enter();
    if(tl - hd >= buffer.length)
      notFull.await();
    buffer[tl++ % buffer.length] = v;
    notEmpty.signal();
    mon.leave();
 }
 public Object get()
        throws InterruptedException {
    mon.enter();
    Object v;
    if (tl==hd) notEmpty.await();
    v = buffer[hd++ % buffer.length];
    notFull.leaveWithSignal();
    return v;
 }
}
\end{lstlisting}

A Monitor must be entered with a call to the method \lstinline'enter()'
and exited with a call to the method \lstinline'leave()'. You may enter
the same monitor more than once, for example, calling one
monitor-protected method from another. Of course, you must eventually
leave as many times as you enter.  

\lstinline'Condition' is an inner class. It must be created within a
monitor object. It represents a condition that a thread may wish to
wait on.  

To wait for condition \lstinline'C' to hold, a thread calls 

\begin{lstlisting}
  C.await();
\end{lstlisting}

To signal that the condition holds, a thread calls 

\begin{lstlisting}
  C.signal();
\end{lstlisting}

If one or more threads are awaiting the condition at the time of a
signal, one of the threads will be given immediate control of the
monitor. The thread executing the \lstinline'signal()' will wait to
reacquire the monitor.  

To simultaneously signal a condition and leave the monitor, you can
call \lstinline'leaveWithSignal()'. It is more efficient than a
\lstinline'signal()' followed by a \lstinline'leave()', since the executing
thread does not have to wait to reacquire the monitor before executing
the \lstinline'leave()'. The method is called with 

\begin{lstlisting}
  C.leaveWithSignal();
\end{lstlisting}

Be sure that you declare the fields of the monitor-protected class to
be \lstinline'volatile'. A Java compiler is permitted to cache fields in
registers. This causes problems for concurrency, since one thread
could change its cached copy of a shared field without storing it into
memory. Then another thread would not see the change in its own cached
copy or in memory. A thread, however, is forced to synchronize shared
fields with their copies in memory when entering or leaving
synchronized sections of code or when executing \lstinline'wait',
\lstinline'notify', or \lstinline'notifyAll'. This permits concurrent
threads to communicate. Unfortunately, when trying to use other
facilities to provide synchronization, such as the \lstinline'Monitor'
class, the compiler doesn't know to synchronize its cache with memory,
so two threads trying to communicate through a monitor-protected class
may not be able to see each other's changes. But if the fields are
declared \lstinline'volatile', the compiler will store into memory on
assignment and fetch from memory on access. This may slow down
execution, but it will permit threads to communicate.  

\subsubsection{Monitor 's Methods}

A thread enters a monitor by calling the \lstinline'enter()' method. It
must call this before accessing the fields of the protected
object. The fields must be declared \lstinline'volatile' for reasons
already given.  

\begin{lstlisting}
  public void enter()
\end{lstlisting}

A thread leaves the monitor by calling the method \lstinline'leave()'. A
thread must not access fields of the protected object after calling
\lstinline'leave()'. Leave throws \lstinline'MonitorException' if the
thread executing this does not have the monitor locked.  

\begin{lstlisting}
  public void leave() throws MonitorException
\end{lstlisting}

To leave the monitor temporarily, a thread may call \lstinline'release()'
. Release returns a \lstinline'MonitorLock' object that can be used to
reenter later. Note that if the thread has entered several monitors,
it can release and reacquire any or all of them, no matter where it is
in the program.  

\begin{lstlisting}
  public MonitorLock release()
\end{lstlisting}

\begin{lstlisting}
  throws MonitorException
\end{lstlisting}


\lstinline'MonitorLock' contains the entry count, the number of times the
monitor has been entered, but not yet left, and the identification of
the monitor and the thread that had it locked.  \lstinline'MonitorLock''s 
\lstinline'reacquire()' method is called reentered the monitor later.


\lstinline'Release' throws \lstinline'MonitorException' if the thread
executing this does not own the monitor.  

\subsubsection{Interface MonitorCondition 's Methods}

Interface \lstinline'MonitorCondition' is implemented by class
\lstinline'Monitor.Condition' (i.e., the local class \lstinline'Condition'
within class \lstinline'Monitor' ). To create a \lstinline'MonitorCondition'
in monitor \lstinline'M', call \lstinline'M.new Condition()'. The purpose
of \lstinline'MonitorCondition' is to allow threads to wait for
conditions to hold and to signal that the conditions hold.  

To wait for the condition to hold, a thread calls the method
\lstinline'await()'. This method throws \lstinline'InterruptedException' if
interrupted while waiting, and \lstinline'MonitorException' if the
executing thread does not own this \lstinline'Monitor'.  

\begin{lstlisting}
  public void await() throws java.lang.InterruptedException,  MonitorException
\end{lstlisting}

A thread calls the method \lstinline'signal()' to signal that the
condition has occurred. If there are any waiting threads, it will wake
up one of them to resume execution, hand over the monitor to it, and
itself wait to reenter the monitor.  \lstinline'Signal' throws
\lstinline'MonitorException' if the executing thread does not own the
\lstinline'Monitor'.  

\begin{lstlisting}
   public void signal() throws MonitorException
\end{lstlisting}

The method \lstinline'leaveWithSignal()' simultaneously signals a
condition and leaves the monitor. It is equivalent to 

\begin{lstlisting}
   public void leaveWithSignal() throws MonitorException
\end{lstlisting}

\begin{lstlisting}
   cond.signal();
   mon.leave();
\end{lstlisting}

If there are any waiting threads, it signals one of them to resume
execution and hands over the monitor to it.  

If the current thread has entered the monitor only once,
\lstinline'leaveWithSignal()' is faster than a call to \lstinline'signal()'
followed by a call to \lstinline'leave()'. The executing thread does not
have to enter the monitor again just to leave it. However, if this
thread has entered the monitor more than once,
\lstinline'leaveWithSignal()' behaves like \lstinline'signal()' followed by
\lstinline'leave()'. After the signaled thread has run, the signaling
thread will reenter the monitor to complete its execution.  

The method \lstinline'leaveWithSignal()' throws
\lstinline'InterruptedException' if the thread is interrupted while
trying to reenter the monitor. It throws \lstinline'MonitorException' if
the thread executing this is not inside the \lstinline'Monitor'.  

\subsubsection{Interface MonitorLock}

The \lstinline'Lock' class within \lstinline'Monitor' (
\lstinline'Monitor.Lock' ) has only one method: \lstinline'reacquire().'  It
is used to enter the monitor again after an earlier \lstinline'release()'
. It throws \lstinline'InterruptedException' if the thread is interrupted
while waiting to enter. It throws \lstinline'MonitorException' if the
thread that called \lstinline'reacquire()' wasn't the thread that
released the monitor.  
                                                                                             

\begin{lstlisting}
   public void reacquire() throws MonitorException
\end{lstlisting}

A \lstinline'Monitor.Lock' object contains a reference to the thread that
executed \lstinline'release()', the monitor it released, and the count
of the number of locks it held on the monitor. The
\lstinline'reacquire()' method reestablishes all the locks the thread had
on the monitor.  

\lstinline'MonitorLocks' and the methods \lstinline'release()' and
\lstinline'reacquire()' are not part of the original specification of
monitors. Almost certainly, the designers of the monitors concept
would not approve of them. They were added as a possibility for
avoiding deadlock. They allow a thread to release several monitors if
it must wait for a condition.  

\section{Examples using Monitor Objects}

\label{96813}

You've already seen two implementations of a bounded buffer
implemented using monitors. We'll show \lstinline'Monitor' objects being
used for implementations of \lstinline'SimpleFuture' (see section      
\ref{SimpleFuture}) and a subset of
\lstinline'SharedTableOfQueues' (whose full implementation is described
in chapter \ref{STOQ}).  

\subsubsection{SimpleFuture} 

The code for our implementation of \lstinline'SimpleFuture' using a
\lstinline'Monitor' object is shown in listing \ref{Listing.SimpleFuture}.
Its fields are 

\begin{itemize}

\item{value : This is the value stored in the future. To indicate that
  there is currently no value present, the value field points to the
  future object itself. (The theory is that one value that the user
  will never wish to put in the future is the future itself.)}

\item{is\underscore{}set : This is a condition variable. Threads that
  try to get the value before it is set wait on this condition.}
\end{itemize}

Recall that a future is a variable that can be assigned only
once. When threads attempt to fetch a value from the future, they are
delayed until the value has been assigned. In the Java implementation,
we could release all threads with a \lstinline'notifyAll()' method
call. With monitors, we cannot awaken all at the same time.  

Class SimpleFuture
\begin{lstlisting}[float, frame=lines, caption=Simple Futures, label=Listing.SimpleFuture]
includesnip: info.jhpc.textbook.chapter04.SimpleFuture:all
\end{lstlisting}

Let's examine the implementation of methods \lstinline'isSet',
\lstinline'getValue', and \lstinline'setValue'.  

\subsection{isSet().}

The way we determine whether a value has been set is by examining the
\lstinline'value' field. If it references this \lstinline'SimpleFuture'
itself, then there is no value present.  

The other conspicuous trick in \lstinline'isSet()' is using
\lstinline'try...return...finally... leave' to leave the monitor after
returning the value. This may not be as obvious as saving the value to
be returned in a variable, leaving the monitor, and then executing a
return statement.  

\subsection{setValue()}

The \lstinline'if' statement at the top of the code tests to see if the
future has already been assigned a value and, if so, to refuse to
reassign it. If the value hasn't been set yet, \lstinline'setValue()'
does the assignment and hands off the monitor to one of the waiting
threads (if there are any). It does not loop and wake them all
up. Each thread that is awakened hands off the monitor to the next
waiting thread.  

\subsection{getValue()}

Method \lstinline'getValue()' is forced to wait if the value hasn't been
assigned yet, but can return immediately if the value has been. It
will throw an \lstinline'InterruptedException' if it is interrupted while
waiting. The \lstinline'try'...  \lstinline'catch' handles leaving the
monitor while interrupted.  

As explained for \lstinline'setValue()', the call to
\lstinline'leaveWithSignal()' hands off the monitor to another waiting
thread. Each of the waiting threads hands off the monitor to the next
as it exits. Since \lstinline'leaveWithSignal()' is equivalent to
\lstinline'leave()' when no threads are waiting, it is okay to call it
even if there are no threads waiting.  

\subsubsection{SharedTableOfQueues}

This implementation of a subset of \lstinline'SharedTableOfQueues' is a
subclass of \lstinline'Monitor'. Its overall structure is shown in
listing \ref{Listing.STOQ}. It uses a hash table to
look up the queues. The queues themselves are represented by the local
class \lstinline'Folder'. (The name was chosen for historical reasons:
It was used in the \lstinline'Memo' system, which provides a distributed
memory communication system based on a shared table of queues.)  

\begin{lstlisting}[float, frame=lines, caption=Shared Table of Queues class, label=Listing.STOQ]
TODO include a summary of this class somehow
include_snip: info.jhpc.textbook.chapter04.SharedTableOfQueues:all
\end{lstlisting}

The class \lstinline'Folder' is used strictly as a data structure. It has
no methods. Its fields are 

\begin{itemize}

\item{q : This is the actual queue. It is an object of class
  QueueComponent which is used in other classes in the thread package
  as well as well.}

\item{notEmpty : This is the Condition that the queue, q, is not
  empty. Threads calling get() wait for this condition. This condition
  is bound to the surrounding SharedTableOfQueue 's Monitor.}

\item{numWaiting : This field counts the number of waiting threads. It
  is used to decide when to remove folders. If there are no values in
  the queue and no threads waiting, the folder may be removed; it will
  be created in exactly the same state if it is referenced again.}

\end{itemize}

The methods are implemented as follows: 

\subsection{put()}
The \lstinline'put(key, value)' method, shown in listing \ref{Listing.Put}, 
puts a \lstinline'value'
into the queue associated with a \lstinline'key'. It uses a hash table
to look up the queue, represented by a \lstinline'Folder' object. The
queue has to be created if one doesn't already exist. The
\lstinline'put()' method leaves the monitor signaling the folder's
\lstinline'notEmpty' condition.  

\begin{lstlisting}[float, frame=lines, caption=The SharedTableOfQueues method put(), label=Listing.Put]
includesnip: info.jhpc.textbook.chapter04.SharedTableOfQueues:put
\end{lstlisting}


\subsection{get()}
The \lstinline'get(key)' (see Listing \ref{Listing.Get}) method has to accomplish several things: 

\begin{itemize}
\item If the key does not already have a folder, one is created.

\item Field \lstinline'numWaiting' is incremented before this thread waits for the
  queue to have something in it and is decremented afterwards.

\item After getting a value from the queue, if the queue is empty and
  there are no threads waiting to remove something from it, \lstinline'get()'
  removes the queue.
\end{itemize}

\begin{lstlisting}[float, frame=lines, caption=The SharedTableOfQueues method get(), label=Listing.Get]
includesnip: info.jhpc.textbook.chapter04.SharedTableOfQueues:get
\end{lstlisting}


\subsection{getSkip()}
Method \lstinline'getSkip(key)' returns immediately, whether or not the
queue contained a value. If there is no folder associated with the key
or if the queue is empty, it simply returns null. Its code is shown in
Listing \ref{Listing.GetSkip}.  

As with \lstinline'get()', \lstinline'getSkip()' removes the queue if it is
empty and no other threads are waiting to get a value from it.  

\begin{lstlisting}[float, frame=lines, caption=SharedTableOfQueues method getSkip(), label=Listing.GetSkip]
includesnip: info.jhpc.textbook.chapter04.SharedTableOfQueues:getSkip
\end{lstlisting}

\section{Implementation of Monitor, Condition, and MonitorLock}
The overall structure of class \lstinline'Monitor' is shown in listing \ref{Listing.Monitor}.  

\begin{lstlisting}[float, frame=lines, caption=High-Level Structure of class Monitor, label=Listing.Monitor]
TODO include a summary of this class somehow
include_snip: info.jhpc.thread.Monitor
\end{lstlisting}

The \lstinline'Monitor' class has three fields. The Semaphore,
\lstinline'monitorEntry', gives exclusive access to the monitor: 

\textbf{\lstinline'Monitor'} Monitorfields

\lstinline'java.lang.Thread current;' The current thread.

\lstinline'Semaphore monitorEntry;' Semaphore to lock the
\lstinline'Monitor'

\lstinline'int monitorEntryCount;' The number of times the monitor's
current owner has entered it minus the number of times it has exited
it.

\begin{itemize}

\item monitorEntry.down() : locks the monitor on entry,

\item monitorEntry.up() : unlocks the monitor on exit.

\end{itemize}

The \lstinline'current' field references the thread that currently
possesses the monitor. It is null if the monitor isn't currently owned
by any thread. The \lstinline'monitorEntryCount' field counts the number
of times the thread that currently owns the monitor has entered it
minus the number of times it has left. Upon leaving the monitor, if
\lstinline'monitorEntryCount' becomes zero, the monitor is unlocked.


\subsubsection{Monitor Entry and Exit}

Method \lstinline'enter()' checks to see if the current thread already
owns the monitor. If so, it merely increments the
\lstinline'monitorEntryCount'. If not, it must seize the monitor by
downing the \lstinline'monitorEntry' semaphore. Once it owns the monitor,
it assigns itself (a reference to its \lstinline'Thread' object) to the
\lstinline'current' field and places an initial count of unity in the
\lstinline'monitorEntryCount' field.  

\begin{lstlisting}[float, frame=lines, caption=The Monitor method enter()]
includesnip: info.jhpc.thread.Monitor:enter
\end{lstlisting}

However, a question concerning many of these methods is, ``How should
they work with \lstinline'InterruptedException' ?'' Our underlying
implementation waits to acquire the monitor by downing semaphores. The
\lstinline'down()' method can throw an \lstinline'InterruptedException'. If
we just pass that through, we could throw
\lstinline'InterruptedException' s on \lstinline'enter()', \lstinline'await()'
, \lstinline'signal()', \lstinline'leaveWithSignal()', and
\lstinline'reacquire()'. Having to put in \lstinline'try' - \lstinline'catch'
statements around all these calls would make \lstinline'Monitors'
inconvenient to use.  

We follow the lead of Java's monitors.  \lstinline'InterruptedException'
will not be thrown upon entering or leaving a monitor, but can be
thrown upon waiting for a condition to be signalled. Thus,
\lstinline'enter()', \lstinline'signal()', \lstinline'leaveWithSignal()',
and \lstinline'reacquire()' should not be able to throw
\lstinline'InterruptedException'. They should, however, preserve the
state of the thread. If the thread was interrupted when it called the
method, it should still be interrupted when it returns.  

This explains the boolean variable \lstinline'interrupted'. This
variable is set if the thread enters the method in an interrupted
state, or if it is interrupted while waiting on a semaphore within the
method. At the end of the method, the thread is again interrupted if
the \lstinline'interrupted' flag is set.  

Thus, we have the following code: 

\begin{lstlisting}
for(;;)
   try {
      monitorEntry.down(); break;
   } catch (InterruptedException ie) {
      interrupted=true;
   }
\end{lstlisting}

The infinite loop will keep catching interrupts while the thread is
trying to enter the monitor. When there is an interrupt, the
interrupted flag is set to allow the thread to be interrupted again
when it leaves the method. If the method successfully downs the
\lstinline'monitorEntry' semaphore, it breaks out of the loop.  

Method \lstinline'leave()' first checks that the thread that called it
actually owns the monitor. If the thread doesn't own the monitor, it
throws an exception. If it does own the monitor, it decrements
\lstinline'monitorEntryCount'. If the count is still greater than zero,
this thread still owns the monitor. If the count goes to zero, the
monitor is free, so \lstinline'leave()' sets the current reference to
null and ups the \lstinline'monitorEntry' semaphore to allow some other
thread to seize the monitor.  

\begin{lstlisting}[float, frame=lines, caption=The Monitor method leave()]
includesnip: info.jhpc.thread.Monitor:leave
\end{lstlisting}

Method \lstinline'release()' allows a thread to temporarily give up all
locks the thread has on a monitor. First, it checks that the thread
executing it owns the monitor. If the thread does not own the monitor,
\lstinline'release()' throws an exception. If it does own the monitor,
\lstinline'release()' creates a \lstinline'Monitor.Lock' object to
return. The initialization for the \lstinline'Lock' object grabs copies
of the \lstinline'Monitor' objects fields \lstinline'current' and
\lstinline'monitorEntryCount'. Then, \lstinline'release()' releases the
monitor.  

\begin{lstlisting}[float, frame=lines, caption=The Monitor method release()]
public MonitorLock release() throws MonitorException {
    if (current != Thread.currentThread())
        throw new MonitorException("release()");
    Lock L = new Lock();
    current = null;
    monitorEntryCount = 0;
    monitorEntry.up();
    return L;
}
\end{lstlisting}

\subsubsection{Monitor.Condition}

The local class \lstinline'Condition' within \lstinline'Monitor' implements
interface \lstinline'MonitorCondition'. It is used to represent
conditions (also known as events) in the Brinch-Hansen and Hoare
monitors.  


\textbf{\lstinline'Monitor.Condition'} Monitor.Conditionfields

\lstinline'Semaphore waitCond;' The semaphore upon which the waiting
threads wait.

\lstinline'int waiting;' The number of threads waiting on this condition.

\lstinline'Condition' has two fields. The \lstinline'waitCond' field is a
semaphore used to delay threads that are waiting on the condition. The
\lstinline'waiting' field is a count of the number of threads waiting on
the semaphore. This count is important, as semaphores maintain the
count of the number of up operations performed, whereas conditon
variables are memoryless. As we will see in \lstinline'signal()', a
signal operation can only be translated into upping the semaphore if
there are threads waiting.  

In the code for the methods in \lstinline'Condition', fields
\lstinline'current', \lstinline'monitorEntry', and
\lstinline'monitorEntryCount' are fields of the surrounding
\lstinline'Monitor' object.  

Method \lstinline'await()' first checks that the executing thread owns
the surrounding monitor. If the thread does not own the monitor, it
throws an exception. If it does own the monitor, it releases the
monitor and waits as follows: 

\begin{itemize}

\item{It saves the monitorEntryCount in the local variable count so it
  can restore it later.}

  % Label
  \label{pgfId-3384}

\item{It marks the monitor as free by setting current to null and
  monitorEntryCount to zero.}

  % Label
  \label{pgfId-3385}

\item{It increments the waiting field of the condition.}

  % Label
  \label{pgfId-3386}

\item{It ups the monitorEntry semaphore to allow another thread to
  enter the monitor.}

  % Label
  \label{pgfId-3387}

\item{It waits on the Condition 's waitCond semaphore.}

  % Label
  \label{pgfId-3388}

\item{Once it's been awakened, it restores its own reference to
  current and the proper count to monitorEntryCount.}

  % Label
  \label{pgfId-3389}

  %\begin{tabular} 
\begin{lstlisting}[caption=The Monitor.Condition method await()]
public void await()
        throws InterruptedException, MonitorException {
    if (current != Thread.currentThread())
        throw new MonitorException("await()");
    int count = monitorEntryCount;
    monitorEntryCount = 0;
    current = null;
    waiting++;
    monitorEntry.up();
    waitCond.down();
    current = Thread.currentThread();
    monitorEntryCount = count;
}
\end{lstlisting}

\end{itemize}

Notice that \lstinline'await()' increments the \lstinline'waiting' field
before waiting on the \lstinline'waitCond' semaphore, but does not
decrement it after being awakened. Methods \lstinline'signal()' and
\lstinline'leaveWithSignal()' handle that. They decrement the count,
because, as soon as they up the semaphore, they awaken the thread,
even if it hasn't started running yet.  

Decrementing the waiting count in \lstinline'signal()' would be
especially important if we were implementing Javalike monitors, where
the currently executing thread continues running inside the monitor or
another thread can seize the monitor before the awakened thread gets
to run. Here's what could happen: Thread \lstinline'X' is the only thread
awaiting a condition. The condition count is one. Thread \lstinline'Y'
signals the condition, so \lstinline'X' is made runnable. But if
\lstinline'Y' doesn't decrement the count, the count will stay one. Now,
thread \lstinline'Y' leaves the monitor, and thread \lstinline'Z' seizes it.
\lstinline'Z' signals the same condition, and since the count is one, it
ups the semaphore again. Since there is no waiting thead, the
semaphore remembers the up in its internal counter.  \lstinline'Z'
leaves, and \lstinline'X' runs. But the next thread, \lstinline'W', that
tries to await the condition will not wait at all, because the
semaphore's counter was greater than zero.  

Decrementing \lstinline'waiting' in \lstinline'signal()' is not as important
here, because the monitor is handed off from one thread to another,
and thus the monitor remains locked, the awakened thread begins
running in it, and the thread that called \lstinline'signal()' queues up
on the \lstinline'monitorEntry' semaphore to reenter the monitor.  

\begin{lstlisting}[caption=The Monitor.Condition method signal()]
public void signal()
        throws MonitorException {
    if (current != Thread.currentThread())
        throw new MonitorException("signal()");
    if (waiting > 0) {
        waiting--;
        int count = monitorEntryCount;
        monitorEntryCount = 0;
        current = null;
        waitCond.up();
        boolean interrupted = Thread.interrupted();
        for (; ;)
            try {
                monitorEntry.down();
                break;
            } catch (InterruptedException ie) {
                interrupted = true;
            }
        current = Thread.currentThread();
        monitorEntryCount = count;
        if (interrupted) current.interrupt();
    }
}
\end{lstlisting}

Method \lstinline'signal()' begins with the usual check that the thread
executing it actually owns the monitor, throwing an exception if it
doesn't.  

If the \lstinline'waiting' count is zero, signal performs no
operation. Otherwise, it must hand off the monitor to one of the
threads waiting for the condition. It does this as follows: 

\begin{itemize}

\item{It decrements the condition's waiting count, for the reasons
  just explained.}

  % Label
  \label{pgfId-3420}

\item{It saves its monitorEntryCount to restore later.}

  % Label
  \label{pgfId-3423}

\item{It clears fields current and monitorEntryCount to denote that it
  has no ownership of the Monitor. This is actually unnecessary.}

  % Label
  \label{pgfId-3424}

\item{It wakes up one waiting thread by upping waitCond.}

  % Label
  \label{pgfId-3425}

\item{It waits to enter the monitor again by downing monitorEntry
. Here, in a way described by enter(), it preserves but ignores the
  fact of the thread being interrupted.}

  % Label
  \label{pgfId-3426}

\item{Once it gets past monitorEntry, it reestablishes fields current
  and monitorEntryCount to denote that it owns the monitor again.}

  % Label
  \label{pgfId-3427}                   

  %\begin{tabular} 
\begin{lstlisting}[caption=The Monitor.Condition method leaveWithSignal()]
public void leaveWithSignal()
        throws MonitorException {
    if (current != Thread.currentThread())
        throw new MonitorException("leaveWithSignal()");
    monitorEntryCount--;
    if (waiting > 0) {
        waiting--;
        if (monitorEntryCount > 0) {
            int count = monitorEntryCount;
            monitorEntryCount = 0;
            current = null;
            waitCond.up();
            boolean interrupted = Thread.interrupted();
            for (; ;)
                try {
                    monitorEntry.down();
                    break;
                } catch (InterruptedException ie) {
                    interrupted = true;
                }
            monitorEntryCount = count;
            current = Thread.currentThread();
            if (interrupted) current.interrupt();
        } else {
            current = null;
            waitCond.up();
        }
    } else {
        if (monitorEntryCount == 0) {
            current = null;
            monitorEntry.up();
        }
    }
}
\end{lstlisting}

\end{itemize}

Method \lstinline'leaveWithSignal()' begins simply enough with checking
that the \lstinline'current' thread owns the monitor and then
decrementing its \lstinline'monitorEntryCount'. Then, alas, there are
four cases to consider: 

\begin{enumerate}

\item{There is a thread waiting at the condition, and
  monitorEntryCount is not zero. The leaveWithSignal() must behave
  like a signal(), since the current thread must continue executing
  in the monitor after the awakened thread has had its chance. This
  code was explained for method signal().}

\item{There is a thread waiting at the condition, and
  monitorEntryCount is zero. The current thread can hand off the
  monitor and continue executing. This only requires three things:}

\item{decrementing the Condition 's waiting count,}

\end{enumerate}

\begin{enumerate}

\item{setting current to null so the current thread can't try to enter
  the monitor again and think it already owns it, and}

\item{upping the Condition 's waitCond semaphore to wake up one
  waiting thread.}

\item{There are no threads waiting at the condition, and
  monitorEntryCount is zero. The current thread must leave the
  monitor. This code was explained in the method leave() from class
  Monitor.}

\item{There are no threads waiting at the condition and
  monitorEntryCount is not zero. The current thread goes on executing
  in the monitor. This doesn't require any code.}

\end{enumerate}

\subsubsection{Monitor.Lock}


\lstinline'Lock' is a class defined in \lstinline'Monitor'. You cannot
create an instance of it directly, but only by calling
\lstinline'Monitor''s \lstinline'release()' method.  

\begin{lstlisting}[caption="Monitor.Lock fields"]
   int n = monitorEntryCount;
   Thread owner = current;
\end{lstlisting}

Method \lstinline'release()' will give up your lock on the monitor, but
will save enough information in the \lstinline'Monitor.Lock' object it
retuns to allow you to reacquire the monitor. It must remember the
following: 

\begin{enumerate}

\item{Who you are, so somebody else cannot reacquire the monitor
  pretending to be you, and}

\item{How many times you have entered the monitor so that it can
  reestablish the proper number of locks.}

\end{enumerate}

There is only one method for a \lstinline'MonitorLock'. Calling
\lstinline'reacquire()' will relock the monitor for you. If a different
thread tries to reacquire the monitor, \lstinline'reacquire()' will throw
a \lstinline'MonitorException'. Since \lstinline'Monitor.Lock' class is
declared within \lstinline'Monitor', \lstinline'reacquire()' can access the
fields of the surrounding \lstinline'Monitor' object directly. Here's
what it does: 

\begin{lstlisting}[caption=The Monitor.Lock method reacquire()]
public void reacquire() throws
        MonitorException {
    if (owner != Thread.currentThread())
        throw new MonitorException("attempt to reacquire Monitor by a different thread");
    boolean interrupted = Thread.interrupted();
    for (; ;)
        try {
            monitorEntry.down();
            break;
        } catch (InterruptedException ie) {
            interrupted = true;
        }
    current = owner;
    monitorEntryCount = n;
    owner = null;
    if (interrupted) current.interrupt();
}
\end{lstlisting}

\begin{itemize}

\item{It checks that the monitor is being reacquired by the same
  thread that released it.}

  % Label
  \label{pgfId-1969}

\item{It locks the monitor by downing the monitorEntry
  semaphore. Again, the interrupted flag is used to preserve the fact
  that the thread has been interrupted while ignoring it in this
  method.}

  % Label
  \label{pgfId-1970}                    

\item{It records that it is the current owner of the monitor.}

  % Label
  \label{pgfId-1971}

\item{It reestablishes the monitor entry count.}

  % Label
  \label{pgfId-1972}

\item{It clears the owner of the Monitor.Lock object so that it cannot
  be used again to enter the monitor.}

  % Label
  \label{pgfId-1973}

\end{itemize}

\section{The Multiple Reader-Writer Monitors}

\label{86119}

Threads that share data structures can run into problems if one of the
threads is writing into the structure while another thread is reading
from it or if two threads try to write into it at the same time. This
is because several values must typically be stored to move the data
structure from one consistent state to another. If only some of the
stores have been made when it is read, the reader will get
confused. If more than one thread is writing into it, some of the
fields may end up changed by one of the threads and other fields
changed by the other. Thereafter, anything reading from it will be
confused.  

The easiest solution is to lock the data structure whenever accessing
it. Any other thread trying to access the structure will have to wait
until it is unlocked before being able to lock the structure itself.


The problem with locking the data structure is that although it is
essential to prevent any thread from writing to the data structure
while another thread is writing to or reading from it, there is no
reason to prevent several threads from simultaneously reading. If many
threads are permitted to read at the same time, we would expect better
performance.  

\subsubsection{Policies}

We present five policies for synchronizing threads trying to read from
or write to a shared data structure: 

\begin{enumerate}

\item{The single reader-writer monitor locks the data structure so
  that only one thread can access the data structure at a time,
  whether the thread is a reader or a writer. It is equivalent to a
  semaphore.}

\item{The writers-preferred monitor gives the shared structure to a
  waiting writer (if there is one) and only if there is no writer
  waiting will it be given to readers. All waiting readers will be
  allowed to access the structure at the same time.}

\item{The readers-preferred monitor gives the shared structure to all
  waiting readers (if there are any) and gives it to a writer only if
  there is no reader waiting.}

\item{The alternating readers-writers monitor gives the shared
  structure to a waiting writer when readers have finished with it and
  to readers when a writer has finished with it.}

\item{The take-a-number monitor gives the shared resource to the
  threads in order of arrival. It requires a kind of busy waiting. The
  threads must check to see whether the number they've taken is now
  being served.}

  %\begin{tabular}

\begin{lstlisting}  These algorithms are animated in: http://www.toolsofcomputing.com.
\end{lstlisting}

\end{enumerate}

The queued reader-writer monitor, presented later in Chapter \ref{Chapter.STOQ}, gives the shared
resource to the threads in order of arrival. It uses a
\lstinline'FutureQueue' from the thread package to give the resource to
the threads in a first-come, first-served order. Unlike the
take-a-number monitor, which also gives the shared resource to the
threads in order of arrival, the queued reader-writer monitor doesn't
require busy waiting.  

The writers-preferred, readers-preferred, and alternating
reader-writer monitors all have complexities in design that are
discussed in their individual sections.  

\subsubsection{Entering and Leaving the Critical Sections}

Readers and writers must explicitly lock and unlock the shared
resource. The locking is done via method calls to a monitor object
that implements the desired policy, as in the following: 

Reader 

\begin{lstlisting}
   monitor.startReading();
   try {
     ...read...
   } finally {
     monitor.stopReading();
   }
\end{lstlisting}

Writer 

\begin{lstlisting}
   monitor.startWriting();
   try {
     ...write...
   } finally {
     monitor.stopWriting();
   }
\end{lstlisting}

The reason for the \lstinline'try...finally' statements is that the
thread could throw an exception within the code to read or write. It
is important to unlock shared resources upon abnormal exit.  

\subsubsection{The Single-Reader-Writer Monitor}

This demonstration shows a simple lock on the data structure. Only a
single reader or writer can access the shared resource at one time.


\begin{lstlisting}[caption="SingleReaderWriter class"]
public class SingleReaderWriter implements MultipleReadersWritersMonitor {
    protected int n = 0;

    public void reset() {
        n = 0;
    }

    public synchronized void startReading()
            throws InterruptedException {
        while (n != 0) wait();
        n = 1;
    }

    public synchronized void stopReading() {
        n = 0;
        notify();
    }

    public synchronized void startWriting()
            throws InterruptedException {
        while (n != 0) wait();
        n = 1;
    }

    public synchronized void stopWriting() {
        n = 0;
        notify();
    }

    public String getMonitorInfo() {
        return "Single Reader Writer Monitor";
    }
}

\end{lstlisting}

With a fair scheduling algorithm, each thread, in turn, should get a
chance to run, cycling through the threads over and over. We've tried
this out on a number of Java implementations. They are not fair. A
small subset of the threads run while all the others wait.  

The Single-Reader-Writer Monitor is equivalent to a lock or binary
semaphore. Methods \lstinline'startReading()' and \lstinline'startWriting()'
are identical, as are \lstinline'stopReading()' and
\lstinline'stopWriting()'.  

\subsubsection{The Readers-Preferred Monitor}

The Readers-Preferred Monitor gives the resource to a reader (if there
are any available). Only if there are no readers present will the
resource be given to a writer.  

If you run this animation with threads choosing randomly whether to
read or write, you will notice that most threads end up waiting to
write for a long time. If you run it with a fixed number of readers,
you will observe the animation alternately giving the resource to a
batch of readers and then to a writer while the readers are inactive.


\subsection{State of the monitor.}

The state of the readers-preferred monitor is contained in four
variables: 

\begin{description}
\item[nr]
The number of threads currently reading nr > = 0.
\item[nw]
The number of threads currently writing (zero or one).
\item[nrtotal]
The number of threads either reading or waiting to read
\item[nwtotal]
The number of threads either writing or waiting to write.
\end{description}

\begin{lstlisting}[caption=The ReadersPreferredMonitor method startReading()]
public synchronized void startReading() throws InterruptedException {
  nrtotal++;
  while (nw!=0) wait();
  nr++;
}
\end{lstlisting}

\subsection{startReading()}

If a thread tries to start reading, it must wait until there are no
threads currently writing; in other words, it must wait until
\lstinline'nw' is zero
\begin{lstlisting}[caption=The ReadersPreferredMonitor method startWriting()]
public synchronized void startWriting() throws InterruptedException{
  nwtotal++;
  while (nrtotal+nw != 0) wait();
  nw=1;
}
\end{lstlisting}

\subsection{startWriting().}

To start writing, a thread must wait until there are no other threads
reading, waiting to read, or writing (i.e., \lstinline'nrtotal' =
\lstinline'nw' = zero).

The ReadersPreferredMonitor method stopReading()
\begin{lstlisting}
public synchronized void stopReading(){
  nr--;
  nrtotal--;
  if (nrtotal==0) notify();
}
\end{lstlisting}


\subsection{stopReading().}

When the last present reader finishes reading, it wakes up a waiting
writer (if there are any present), which will seize the monitor and
start writing.  

The ReadersPreferredMonitor method startWriting()
\begin{lstlisting}
public synchronized void stopWriting(){
  nw=0;
  nwtotal--;
  notifyAll();
}
\end{lstlisting}

\subsection{stopWriting().}

When a writer finishes writing, it wakes up all waiting readers and
writers to let them compete for the monitor.  

\subsubsection{The Writers-Preferred Monitor}

A Writers-Preferred Monitor gives the resource to a writer if any is
waiting. Only if there is no writer available will it be given to
readers.  

If you run this animation with threads choosing randomly whether to
read or write, you will observe that more and more threads accumulate
waiting to read until there are no writers left. Then, all the waiting
readers will run.  

If you run it with a fixed set of readers, a batch of readers may run
before the first writer enters the monitor, but thereafter, typically,
all the writers will run to completion before any readers run
again. (You can set the number of readers and rest time to give the
readers a better chance.)  

\subsection{State of the monitor.}

The state of the monitor is contained in four variables: 

\begin{description}
\item[nr]
The number of threads currently reading.

\item[nw]
The number of threads currently writing (zero or one).

\item[nrtotal]
The number of threads either reading or waiting to read. (nrtotal >= nr).

\item[nwtotal]
The number of threads either writing or waiting to write.
\end{description}

The WritersPreferredMonitor method startReading
\begin{lstlisting}
public synchronized void startReading()
  throws InterruptedException{
  nrtotal++;
  while (nwtotal!=0) wait();
  nr++;
  }
\end{lstlisting}

\subsection{startReading().}

If a thread tries to start reading, it must wait until there are no
threads either writing or waiting to write; in other words, it must
wait until \lstinline'nwtotal' is zero.  

The WritersPreferredMonitor method startWriting
\begin{lstlisting}
public synchronized void startWriting()
  throws InterruptedException{
  nwtotal++;
  while (nr+nw != 0) wait();
  nw=1;
  }
\end{lstlisting}

\subsection{startWriting().}

To start writing, a thread must wait until there are no other threads
reading or writing, indicated by \lstinline'nr' and \lstinline'nw' both
equaling zero.  

The WritersPreferredMonitor method stopReading()
\begin{lstlisting}
public synchronized void stopReading(){
  nr--; nrtotal--;
  if (nr==0) notifyAll();
  }
\end{lstlisting}

\subsection{stopReading().}

When the last reader of a group finishes reading, it wakes up all
waiting readers and writers. If there are any waiting writers, no
reader will be able to start reading, but will wait again. Eventually,
a writer will seize the monitor and start writing.  

The WritersPreferredMonitor method stopWriting()
\begin{lstlisting}
public synchronized void stopWriting(){
  nw=0; nwtotal--;
  notifyAll();
  }
\end{lstlisting}

\subsection{stopWriting().}

When a writer finishes writing, it wakes up all waiting readers and
writers to let them compete for the monitor.  

\subsubsection{The Alternating Readers-Writers Monitor}

The idea of the Alternating Readers-Writers Monitor is that readers
and writers should take turns. Trying to specify this a bit more
carefully, we come up with the following elements: 

\begin{itemize}

\item{General alternation. A batch of readers run, followed by a
  single writer, followed by another batch of readers, etc.}

  % Label
  \label{pgfId-2136}

\item{Immediate access. If a reader arrives and there are no writers
  present, it is given access to the resource immediately. If a writer
  arrives and neither readers nor writers own the resource, it is
  allocated the resource immediately.}

  % Label
  \label{pgfId-2137}

\end{itemize}

\subsection{State of the monitor.}

The state of an Alternating Readers-Writers Monitor is contained in
four variables: 

\begin{description}

\item[nr]
The number of threads (array of dimension 2) currently reading.

\item[thisBatch]
Index in nr of the batch of readers currently reading (zero or one).

\item[nextBatch]
Index in nr of the batch of readers waiting to read (always 1-thisBatch).

\item[nw]
The number of threads currently writing (zero or one).

\item[nwtotal]
The number of threads either writing or waiting to write.
\end{description}

The AlternatingReadersWritersMonitor method startReading()
\begin{lstlisting}
public synchronized void startReading()
  throws InterruptedException{
  if (nwtotal==0) nr[thisBatch]++;
  else {
  nr[nextBatch]++;
  int myBatch=nextBatch;
  while (thisBatch!=myBatch) wait();
  }
  }
\end{lstlisting}

\subsection{startReading().}

When a thread tries to start reading, it checks first to see if there
are any writers present. If there are none, it starts reading
immediately, recording its presence in \lstinline'nr[thisBatch]'.  

If there are writers present, it must wait until one writer has run,
so it adds itself to the number of readers in the next batch by
incrementing \lstinline'nr[nextBatch]'. It saves the value of
\lstinline'nextBatch' in the variable \lstinline'myBatch' and waits until
\lstinline'thisBatch' equals \lstinline'myBatch', which will indicate that
a writer has finished running.  

The AlternatingReadersWritersMonitor method stopReading()
\begin{lstlisting}
public synchronized void stopReading(){
  nr[thisBatch]--;
  if (nr[thisBatch]==0) {
  notifyAll();
  }
  }
\end{lstlisting}

\subsection{stopReading().}

When a thread stops reading, it subtracts itself from
\lstinline'nr[thisBatch]'. It then notifies all waiting threads to try
accessing the resources. Readers will wait again, since
\lstinline'thisBatch' has not been set to the value they are waiting for,
but one of the writers will be able to start writing.  

The AlternatingReadersWritersMonitor method startWriting()
\begin{lstlisting}
public synchronized void startWriting()
  throws InterruptedException{
  nwtotal++;
  while (nr[thisBatch]+nw != 0) wait();
  nw=1;
  }
\end{lstlisting}

\subsection{startWriting()}

When a writer attempts to start writing, it adds itself to the total
number of writers present. Then, it waits until no threads are reading
or writing. Once that condition is true, it sets \lstinline'nw' to one to
indicate that it is writing and begins writing.  

The AlternatingReadersWritersMonitor method stopWriting( )
\begin{lstlisting}
public synchronized void stopWriting(){
  nw=0; nwtotal--;
  int tmp=thisBatch;
  thisBatch=nextBatch;
  nextBatch=tmp;
  notifyAll();
  }
\end{lstlisting}

\subsection{stopWriting().}

When a thread stops writing, it sets \lstinline'nw' back to zero to
indicate that no thread is writing, and it subtracts itself from the
total number of writers present. It then swaps the values of
\lstinline'thisBatch' and \lstinline'nextBatch' to release the next batch of
readers, and it notifies all waiting threads, which wakes up the
readers.  

\subsubsection{The Take-a-Number Monitor}

\label{36307}

As each reader or writer arrives, it takes the next number, and
threads are served in order by their number. However, all readers with
consecutive numbers are served at the same time.  

\subsection{State of the monitor.}

The state of this monitor is contained in three variables: 

\begin{description}

\item[nr]
The number of threads currently reading.

\item[nextNumber]
The number to be taken by the next thread to arrive.

\item[nowServing]
The number of the thread to be served next.
\end{description}

The TakeANumberMonitor method startReading()
\begin{lstlisting}
public synchronized void startReading()
  throws InterruptedException{
  int myNumber = nextNumber++;
  while (nowServing!=myNumber) wait();
  nr++;
  nowServing++;
  notifyAll();
  }
\end{lstlisting}

\subsection{startReading().}

If a thread tries to start reading, it takes a number and waits until
its number comes up. Then, it increments the number of readers and the
number currently being served. By incrementing \lstinline'nowServing', a
reader allows the reader with the next sequential number to start. If
the thread with the next number is a writer, it will wait until the
readers are done before starting.  

The TakeANumberMonitor method startWriting()
\begin{lstlisting}
public synchronized void startWriting()
  throws InterruptedException{
  int myNumber = nextNumber++;
  while (nowServing!=myNumber) wait();
  while(nr>0) wait();
  }
\end{lstlisting}

\subsection{startWriting().}

To start writing, a thread takes a number, waits until its number
comes up, and then waits until any preceding readers are finished. It
will not increment \lstinline'nowServing' until it is finished writing,
since no subsequent thread should run until this writer is done.  

The TakeANumberMonitor method stopReading()
\begin{lstlisting}
public synchronized void stopReading(){
  nr--;
  if (nr==0) notifyAll();
  }
\end{lstlisting}

\subsection{stopReading()}

When the last present reader finishes reading, it wakes up a waiting
writer (if there is one present). Unfortunately, it has to wake up all
threads just for one of them to start writing.  

The TakeANumberMonitor method stopWriting()
\begin{lstlisting}
public synchronized void stopWriting(){
  nowServing++;
  notifyAll();
  }
\end{lstlisting}

\subsection{stopWriting()}

When a writer finishes writing, it increments \lstinline'nowServing' and
wakes up all waiting readers and writers to let them see if they are
next.  

\section{Chapter Wrap-up}

\label{85396}

We discussed what monitors are supposed to be and observed that Java's
synchronized methods provide degenerate forms of monitors. We then
studied the thread package's \lstinline'Monitor' class, which provides
more of the facilities of monitors, but without any of the syntactic
support. The implementation of \lstinline'Monitor' and related classes
shows sophisticated uses of semaphores.  

We then considered multiple reader-writer monitors, which provide
shared access to resources for readers, but mutual exclusion for
writers. The different implementations provide different scheduling
policies. The readers-preferred monitor gives readers priority over
writers. The writers-preferred monitors do exactly the opposite. The
alternating readers-writers monitor alternates between giving access
to a single writer and a batch of readers. The take-a-number monitor
gives access to threads in first-come, first-served order while
alternating between single writers and batches of readers. A tricky
problem in implementing these monitors is properly allocating a
monitor to a newly arriving thread when no thread is currently using
it and no threads are queued for it when the new thread arrives.  

\section{Exercises}

\label{35398}

\begin{enumerate}

\item
The language Python provides lock objects similar to binary
semaphores (i.e., semaphores for which the count is either zero or
one). Here are the facilities of a Java version of Python locks: 

The constructor 

\begin{lstlisting}
  Lock L=new Lock();
\end{lstlisting}

creates a \lstinline'Lock' object, which is initially unlocked. The
method 

\begin{lstlisting}
  L.acquire();
\end{lstlisting}

which locks the \lstinline'Lock' object (similarly to \lstinline'down()' for
a semaphore). It blocks the thread's execution until the \lstinline'Lock'
object is available. The call 

\begin{lstlisting}
  boolean a=L.acquire(false);
\end{lstlisting}

will immediately return, saying whether it acquired the lock. It
assigns \lstinline'true' to \lstinline'a' if the lock was acquired. If the
lock wasn't acquired, it assigns \lstinline'false'. The call
\lstinline'L.acquire(true)' is equivalent to \lstinline'L.acquire()'. The
method 

\begin{lstlisting}
  L.release();
\end{lstlisting}

releases a lock, allowing another thread to acquire it. A blocked
thread waiting for the lock is given the chance to acquire it.  

If a thread tries to lock the same \lstinline'Lock' object more than
once, it is deadlocked with itself.  

Implement \lstinline'Lock' objects in Java that provide the facilities of
Python locks.  

\item
Python provides reentrant locks similar to the monitors in Java
that allow the same thread to synchronize more than once on the same
object. For that matter, they are like the monitors described in this
chapter, which allow a thread to enter the same monitor more than once
before leaving it. The Java version is as follows: 

The constructor call 

\begin{lstlisting}
  RLock L=new RLock();
\end{lstlisting}

creates a reentrant lock. The operations on an \lstinline'RLock' object
are the same as on a \lstinline'Lock' object, except that a thread will
not block itself if it tries to acquire the same lock more than once
before releasing it. The \lstinline'RLock' object is not released for
other threads until the thread that owns it has released it as many
times as it has acquired it.  

Implement \lstinline'RLock' objects in Java that provide the facilities
of Python \lstinline'RLocks'.  

\item
The language Python provides \lstinline'Condition' objects similar to
the \lstinline'Monitor.Condition' objects in the thread package. The
following is a Java syntax for them: 

The constructor call 

\begin{lstlisting}
  Condition C=new Condition(L);
\end{lstlisting}

creates a \lstinline'Condition' object that uses underlying \lstinline'Lock'
or \lstinline'RLock' object \lstinline'L'. If \lstinline'L' is omitted, as in


\begin{lstlisting}
  Condition C=new Condition();
\end{lstlisting}

a new \lstinline'RLock' object is created for the \lstinline'Condition'
. The call 

\begin{lstlisting}
  C.acquire();
\end{lstlisting}

locks the underlying \lstinline'Lock' object. It blocks until the lock
object is available. Call 

\begin{lstlisting}
  boolean a=C.acquire(false);
\end{lstlisting}

will return immediately, saying whether it acquired the lock or
not. It assigns \lstinline'true' to \lstinline'a' if the lock was
acquired. If the lock wasn't acquired, it assigns \lstinline'false'. The
call \lstinline'C.acquire(true)' is equivalent to \lstinline'C.acquire(),'
and 

\begin{lstlisting}
  C.release();
\end{lstlisting}

releases the underlying lock. The method 

\begin{lstlisting}
  C.wait();
\end{lstlisting}

must only be called by the thread that has acquired the lock. It
releases the lock and waits until some other thread calls
\lstinline'C.notify()' or \lstinline'C.notifyAll()'. The method 

\begin{lstlisting}
  C.wait(timeout);
\end{lstlisting}

will wait until awakened by \lstinline'notify()' or \lstinline'notifyAll()'
or until \lstinline'timeout' seconds have elapsed. The parameter
\lstinline'timeout' is a floating-point number, so fractions of a second
may be specified. Calling 

\begin{lstlisting}
  C.notify();
\end{lstlisting}

will awaken at most one thread waiting on a \lstinline'Condition'. If no
threads are waiting, \lstinline'notify()' performs no operation. Method
\lstinline'notify()' may only be called by the thread that has acquired
the condition's lock. As in Java, a thread being awakened must
reacquire the lock before returning from \lstinline'wait()'. The thread
executing the \lstinline'notify()' does not simultaneously release the
lock, so the awakened thread will be delayed. Other threads may
acquire the lock before the waiting thread does. The method 

\begin{lstlisting}
  C.notifyAll();
\end{lstlisting}

will awaken all waiting threads. The same caveats apply to it as for
\lstinline'notify()'.  

Implement a \lstinline'Condition' class whose objects behave in the
fashion just described.  

\end{enumerate}
